/*
 * @lc app=leetcode.cn id=5 lang=java
 *
 * [5] 最长回文子串
 */

// @lc code=start
class Solution {

    // 中心扩张算法，分两种情况
    // [23 ms, 87.17 % ], [41.3 MB, 76.74 %]
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2)
            return s;
        int startIndex = 0, endIndex = 0;
        int maxLen = 0;
        for (int i = 0; i < len - 1; i++) {
            int j = 1;
            while (i - j >= 0 && i + j < len && s.charAt(i - j) == s.charAt(i + j)) {
                j++;
            }
            int tj = 2 * j - 1;
            if(tj > maxLen) {
                maxLen = tj;
                startIndex = i - j + 1;
                endIndex = i + j - 1;
            }

            if(s.charAt(i) == s.charAt(i + 1)){
                int k = 1;
                while(i - k >= 0 && i + 1 + k < len && s.charAt(i - k) == s.charAt(i + 1 + k)){
                    k ++;
                }
                int tk = 2 * k;

                if(tk > maxLen) {
                    maxLen = tk;
                    startIndex = i - k + 1;
                    endIndex = i + k;
                }
            }
        }
        return s.substring(startIndex, endIndex + 1);
    }
}
// @lc code=end
// 
// 	// 方法一：暴力解法
//     public String longestPalindrome01(String s) {
//         int len = s.length();
//         for(int i=len; i>0; i--){
//         	for(int j = 0; j<len-i+1; j++){
//         		String sub = s.substring(j,j+i);
//         		int subLen = sub.length();
//         		int index=0;
//         		int half = subLen / 2;
//         		while(index <= half && sub.charAt(index) == sub.charAt(subLen - index - 1)) index++;
//         		if(index > half) return sub;
//         	}
//         }
//         return "";
//     }
// 
//     // 方法二： 最长公共子串
//     public String longestPalindrome02(String s) {
//     	String rs = (new StringBuffer(s)).reverse().toString();
//     	int len = s.length();
//     	for(int i=len; i>0; i--){
//         	for(int j = 0; j<len-i+1; j++){
//         		String sub = s.substring(j, j+i);
//         		if(rs.contains(sub) && rs.indexOf(sub) == len - j -i ) return sub;        	
//         	}
//         }
//     	return "";
// 	}
// 
// 	// 方法三：中心扩展算法
//     public String longestPalindrome(String s) {
//     	String result = "";
//     	int len = s.length();
//     	if(len > 0){
// 	    	int left = 0, right = 0;
// 	    	for(int i = 0; i < len; i++){
// 	    		int count1 = expand(s,i,i);
// 	    		if(count1 * 2 - 1 > right - left +1) {
// 	    			left = i -count1 +1;
// 	    			right = i + count1 -1;
// 	    		}
// 	    		int count2 = expand(s,i,i+1);
// 	    		if(count2 * 2 > right - left +1){
// 	    			left = i - count2 +1;
// 	    			right = i + count2;
// 	    		}
// 	    	}
// 	    	result = s.substring(left,right + 1);
// 		}
//     	return result;
//     }
// 
//     private int expand(String s, int l, int r){
//     	int len = s.length();
//     	int count = 0;
//     	while (l >= 0 && r < len && s.charAt(l) == s.charAt(r)) {
//     		l--;
//     		r++;
//     		count++;
//     	}
//     	return count;
//     }
